{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> 本文将从梯度下降算法开始，然后介绍梯度提升算法，并剖析其原理。最后讨论以下两者的关系。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "基本原理：根据当前模型损失函数的负梯度信息来训练新加入的弱分类器，然后将训练好的弱分类器以累加的形式结合到现有模型中。采用决策树作为弱分类器的Gradient Boosting算法被称为GBDT。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 梯度下降\n",
    "在机器学习任务中，需要最小化损失函数$L(\\theta)$，其中是$\\theta$要求解的模型参数。**梯度下降法通常用来求解这种无约束最优化问题**，它是一种迭代方法：选取初值$\\theta_0$，不断迭代，更新$\\theta$的值，进行**损失函数的极小化**。这里我们还需要初始化算法终止距离$\\varepsilon $以及步长$\\alpha$。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "我们知道梯度下降的核心在于参数的迭代更新$$\\theta_t=\\theta_{t-1}-\\alpha*\\frac{\\partial L(\\theta)}{\\partial \\theta}$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "那么，为什么参数是这样的更新的？我们可以从数学角度，利用泰勒公式推导出来。\n",
    "\n",
    "首先回顾下泰勒公式的内容![](泰勒公式.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**梯度下降算法的推导**\n",
    "1. 写出参数的迭代公式$$\\theta_t=\\theta_{t-1}+\\Delta \\theta$$\n",
    "2. 将$L(\\theta)$在$\\theta_{t-1}$出进行一阶泰勒展开（可以套用泰勒公式的迭代形式得出）$$L(\\theta)=L(\\theta_{t-1}+\\Delta \\theta)≈L(\\theta_{t-1})+L'(\\theta_{t-1}) \\Delta \\theta$$\n",
    "3. 欲使$L(\\theta_t)<L(\\theta_{t-1})$  （这里是希望损失函数下降），可取$\\Delta \\theta = -\\alpha L'(\\theta_{t-1})$，则$\\theta_t-\\theta_{t-1}=\\Delta \\theta = -\\alpha L'(\\theta_{t-1}) \\Longrightarrow \\theta_t=\\theta_{t-1}-\\alpha*L'(\\theta_{t-1})$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**注/后话**：GBDT在模型训练时只使用了代价函数的一阶导数信息，XGBoost对代价函数进行二阶泰勒展开，可以同时使用一阶和二阶导数。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 梯度提升\n",
    "我们知道，梯度下降是希望学习出新的参数来拟合模型的经验损失。而**梯度提升的思想**很类似，它是希望**学习出新的基学习器$h_m$**来**拟合**真实值$y$与当前学习器$f_{m-1}(x)$之间的**残差近似值**（特别地，当使用平方损失函数时，拟合的就是残差）。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**如何理解梯度提升中，基学习器是在拟合真实值与当前学习器之间的残差近似值？**我们可以从泰勒公式推导出来。\n",
    "\n",
    "**梯度提升算法的推导（类比梯度下降算法的推导）**\n",
    "1. 损失函数$L(y,f(x))$在$f_{t-1}(x)$处的一阶泰勒展开式为$$L(y,f(x))≈L(y,f_{t-1}(x))+\\left [ \\frac{\\partial L(y,f(x))}{\\partial f(x)}  \\right ] _{f(x)=f_{t-1}(x)}(f(x)-f_{t-1}(x))$$\n",
    "2. 将$f(x)=f_t(x)$带入上式，得$$L(y,f_t(x))≈L(y,f_{t-1}(x))+\\left [ \\frac{\\partial L(y,f(x))}{\\partial f(x)}  \\right ] _{f(x)=f_{t-1}(x)}(f_t(x)-f_{t-1}(x))$$\n",
    "3. 欲使$L(y,f_t(x))<L(y,f_{t-1}(x))$，可取$f_t(x)-f_{t-1}(x)=\\alpha*\\left (-\\left [ \\frac{\\partial L(y,f(x))}{\\partial f(x)}  \\right ] _{f(x)=f_{t-1}(x)} \\right) \\Longrightarrow f_t(x)=f_{t-1}(x)+\\alpha*\\left (-\\left [ \\frac{\\partial L(y,f(x))}{\\partial f(x)}  \\right ] _{f(x)=f_{t-1}(x)} \\right)$。特别地，当$L(y,f(x))=\\frac{1}{2}(y-f(x))^2$（采用平方损失）时，$f_t(x)-f_{t-1}(x)=\\alpha*(y-f_{t-1}(x)) \\Longrightarrow f_t(x)=f_{t-1}(x)+\\alpha*(y-f_{t-1}(x))$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 梯度下降 vs 梯度提升\n",
    "两者都是在每一轮迭代中，利用损失函数相对于模型的负梯度方向的信息来对当前模型进行更新。只不过在梯度下降中，模型是以参数化形式表示，从而模型的更新等价于参数的更新。而在梯度提升中，模型并不需要进行参数化表示，而是直接定义在函数空间中，从而大大扩展了可以使用的模型种类。![](梯度下降vs梯度提升.png)\n",
    "\n",
    "**提升算法的演进：**\n",
    "\n",
    "前向分布算法 => 提升树（前向分布算法+决策树），如AdaBoost => 梯度提升算法 => 梯度提升树（梯度提升算法+CART），如GBDT => XGBoost => LightGBM，CatBoost（这两者差不多时间提出）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 参考\n",
    "1. [梯度提升（Gradient Boosting）算法](https://mp.weixin.qq.com/s?__biz=MzI5NDMzMjY1MA==&mid=2247485110&idx=1&sn=86bcdb38f51fc5f82236b35c349ada4b&scene=21#wechat_redirect)\n",
    "2. [梯度提升（Gradient Boosting）算法](http://www.360doc.com/content/19/0713/18/1353678_848501530.shtml)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
